The present disclosure relates generally to error correction techniques for data communications and more specifically to stopping rules for iterative decoders.
Error correction coding is a method whereby a sequence of digital information symbols (information bits if binary) are mapped onto another sequence of digital symbols (coded bits if binary) in such a way that redundancy is introduced. The coded symbols are modulated and transmitted across a communications channel that introduces uncertainty as to the actual value of the coded symbols. Error correction coding introduces redundancy that allows the receiver to determine the values of information symbols more reliably.
Error correction coding is often referred to as Error Control Coding (ECC), Forward Error Correction/Control (FEC), or simply coding. The field of coding is well established in both the research literature and engineering practice. Standard models for designing and evaluating coding schemes include three components: (i) the encoder, which maps the information symbols to the coded symbols; (ii) the channel, which introduces uncertainty; and (iii) the decoder, which attempts to determine the values of the information symbols that were transmitted. The channel is typically modeled statistically and this model typically includes the physical propagation channel and other components in the communication system. For example, the channel model can include the modulator and demodulator operations performed at the transmitter and receiver, respectively. FIG. 1 is a simplified diagram of a basic system model.
The most common case considered in the literature is that of a binary information sequence, binary coded symbols, and a memoryless channel. The two most common channel models are the Binary Symmetric Channel (BSC) and the Binary Antipodal Additive White Gaussian Noise (BI-AWGN) Channel.
As an example, an encoder may accept information bits in groups of size K and produce N coded bits, with N>K. The rate of this code is r=K/N and measures the rate of information bits per channel use on the binary channel. In FIG. 1 the information bit sequence is denoted by b[i] (110), the coded bit sequence is denoted by c[j] (120), and the output of the channel is denoted by z[j] (130). The variable in brackets represents time index (e.g., b[10] is the information bit at time index 10). Because the channel is modeled as memoryless, it is described statistically by the probability law for the channel output (z[j]) given the value of the channel input (c[j]) at the same time.
With the BSC model, the channel output z[j] is binary and the channel is described by the probability that z[j] is not equal to c[j]. Specifically, the model assumes that P(z[j]=0|c[j]=1)=P(z[j]=1|c[j]=0)=p. The decoder produces a decision on the value of each information bit, and the probability of error in this decision is less than p for cases when coding has utility. This gives rise to the term error correction since the BSC introduces errors and the code ‘corrects’ these errors.
In the BI-AWGN model, the channel output z[j] is real-valued and the channel is described by the set of probability density functions (pdfs) of z[j] conditioned on each value of c[j]. In the BI-AWGN model, the pdf of z[j] is Gaussian with variance determined by the noise level and mean determined by the value of c[j]. Specifically, the mean is +m if c[j]=0 and −m if c[j]=1, where m is a constant dependent on the channel signal to noise ratio (SNR). Note that in this case it is less natural than that of the BSC to interpret the channel as introducing errors. However, if one were to determine c[j] based only on the value of z[j], ignoring all redundancy introduced in the coded bit sequence by the encoder, then a good rule is to determine that c[j] is 0 if z[j]>0, otherwise c[j] is 1. In fact, if the decoder only has access to the sign of z[j], from the point of view of the decoder the channel is equivalent to a BSC. The larger the absolute value of z[j], the less statistically likely that this implied decision is incorrect. Thus, in the BI-AWGN case, the sign of z[j] contains information about the best memoryless decision on c[j] (i.e., not exploiting the code structure), and |z[j]| provides a level of confidence in this decision.
A channel output that contains both an implicit decision on the channel input (e.g., 0 or 1) and a measure of confidence on this decision is said to be a soft decision or to contain soft decision information. In contrast, a channel output without confidence information is said to be a hard decision. The BSC is an example of a channel with outputs that are hard decisions on the channel input whereas the BI-AWGN is an example of a channel with outputs that are soft decisions on the channel inputs. More generally, the notion of soft decision information extends to any digital variable (e.g., one may consider a soft decision on the information bits). A decoder that utilizes soft decision information from the channel outputs (i.e., decoder inputs) is referred to as a soft decision decoder or a soft-in decoder. Conversely, if the decoder accepts hard decisions as inputs, it is a hard decision decoder or a hard-in decoder. Used properly, soft decision information provides performance gains relative to hard decision decoding. In practice, the real-valued channel output z[j] will be quantized to a finite number of values for digital implementation of the decoder. This is still a form of soft decision information.
While FEC has been utilized in practical communication systems for many years, the advent of Turbo codes in the 1990's provided a significant advance in the state of the art. Subsequent to the introduction of Turbo codes, many codes were introduced that shared many characteristics of Turbo codes. The resulting class of codes is known as modern codes, turbo-like codes, iteratively decodable codes, or codes on sparse graphs. The common characteristics of a modern coding system (i.e., a coding system employing modern codes) are: (i) modeling the code constraints as a group of local code constraints; and (ii) iterative decoding of these local codes.
FIG. 2 is a simplified diagram of an encoder in a Turbo coding system. The system includes two encoders that encode the information bits. One encoder accepts as inputs the information bits (200) in the order that they are input to the Turbo encoder. The information bits are reordered by a permutation or interleaver before being input (220) to the second encoder. Coded bits produced by the two encoders (210, 230) may be punctured to produce the coded bit sequence (240) that is transmitted across the channel.
FIG. 3 is a simplified diagram of an iterative decoder in a Turbo coding system. The iterative decoder accepts the channel outputs (300) as inputs. Typically, these inputs to the decoder contain soft-decision information. The iterative decoder routes the set of channel outputs (310) corresponding to channel inputs from encoder 1 to a decoder for code 1 and routes the set of channel outputs (320) corresponding to channel inputs from encoder 2 to a decoder for code 2.
The iterative decoder is based on soft-in/soft-out (SISO) information for each of the codes. A SISO decoder accepts soft decision information on all variables associated with the corresponding encoder. This is the so-called soft-in information. In the present example, the SISO for code 1 will accept soft decision information on all variables associated with encoder 1. After the SISO decoding process, new (updated) soft decision information is produced. This is the so-called soft-out information. In general, this is new soft decision information on all variables associated with the corresponding code. This process of accepting input soft-in information, executing a SISO decoder, and producing soft-out information is referred to as an activation of the SISO decoder.
The soft decisions processed and exchanged by an iterative decoder are commonly referred to as beliefs, messages and metrics owing to the fact that they may be stored in various formats and therefore interpreted differently.
For the turbo code example, iterative decoding comprises a sequence of activations of the two SISO decoders with an exchange of soft decision information. The sequence of activation is called the activation schedule of the iterative decoder. In general, the activation schedule is not unique and is part of the iterative decoder design.
An activation schedule for the iterative decoder for the turbo codes may be as follows. First, activate SISO decoder 1, interleave the resulting updated soft decisions (330) on the information bits to provide soft-in information (340) to SISO 2, activate SISO 2 producing updated soft decisions (350), and deinterleave these updated soft decisions to provide soft-in information (360) to SISO 1. This sequence defines one iteration, and the iterative decoder will repeat this sequence multiple times—i.e., the iterative decoder runs multiple iterations. The initial activation of SISO 1 may occur with no soft-in information on the inputs to encoder 1. The interleaving of soft-decision information is a reordering of the time indices of this information. The deinterleaving operation is similar but uses the inverse of the permutation defining the interleaver.
The confidence level of soft decisions on the information bits (i.e., the inputs to SISO 1) should increase with more iterations. After the final iteration has been run, these soft decisions provide the final hard decisions on the information bits. A stopping rule is required to determine the final iteration. The convergence of iterative decoders is not guaranteed, although in practice the decisions on the information bits are often observed to stabilize.
The stopping rule may affect the latency, complexity, power consumption, and performance of the iterative decoder. One simple stopping rule is to run experiments to determine the information bit error rate (BER) as a function of the number of iterations run. The results of this experiment can be used to determine a number of iterations to be used that yields a good balance of performance and complexity. FIG. 4 shows a typical plot of bit error rate as a function of bit energy to noise power ratio (Eb/No) based on number of iterations. It is common for the BER performance of the iterative decoder to stabilize with increasing iterations. For example, as shown in FIG. 4 there is very little improvement in BER performance beyond 4 iterations. Since the latency and computational complexity of decoding is proportional to the number of iterations, in practice one would choose the minimum number of iterations necessary to achieve desired performance benefits. This approach leads to a stopping rule that runs a fixed number of iterations. This is the default stopping rule in the research literature—i.e., most performance results are presented with the number of iterations and this number is fixed as described above. This will be referred to as the fixed-iterations rule.
The fixed-iterations rule does not take into account the information produced by the decoder during the decoding of a particular set of channel measurements. Instead, it uses the average behavior over many decoding runs. Alternatively, one could monitor the soft-information being produced by the decoder and stop when it appears to have stabilized. The resulting stopping rules are referred to as early stopping rules. As an example, considering the turbo code iterative decoder, once all soft-decisions on the information bits have stabilized (i.e., converged), one may stop the decoding and provide final hard decisions.
Typically, early stopping rules have a fixed maximum number of iterations and therefore reduce the average number of iterations performed but not the maximum number of iterations. When comparing an early stopping rule to a fixed-iterations rule, the early stopping rule should result in little or no BER performance degradation and have a reduced average number of iterations. A number of early stopping algorithms have been presented in the literature with results presented in terms of this trade off.
The average decoding latency and computational complexity of an iterative decoder is proportional to the average number of iterations run. This average is with respect to decoding blocks. For some blocks the iterative decoder will converge quickly and will be stopped early, while others will utilize the maximum number of iterations. This results in a decoding algorithm with variable complexity and latency. For non-real-time applications, such as computer simulation, these benefits in the average characteristics may be directly beneficial.
For real-time applications, however, taking advantage of these average improvements may not be possible. When the average number of iterations is reduced, the average computational complexity of the decoder is decreased and this will typically decrease the average power consumption of the decoder. It is more difficult to capitalize on a reduction of the average decoding latency. This is because the maximum number of iterations determines the maximum decoding latency. For example, a fixed-iterations decoder with 20 iterations will have the same maximum latency as a decoder with early stopping using a maximum of 20 iterations but yielding an average of 10 iterations. The maximum latency determines the throughput speed of the decoder that can be guaranteed.
To benefit from reduced average decoding latency in a real-time system, the decoder can be augmented with an iteration control unit (ICU). This unit will monitor the number of iterations required for each decoding block and vary the maximum allowable number of iterations. The goal of the iteration control unit is to average out the effects of the variable decoding latency with minimal impact on the BER performance. For example, consider an early stopping rule that provides an average of 10 iterations with a maximum of 20 iterations. If the decoder was stopped early (say at 5 iterations) for many of the previous blocks, the ICU would set the maximum number of iterations at 20 for the current block. However, if many of the previous blocks required 20 iterations to decode, then the ICU would decrease the maximum number of iterations for the current block (say to 12 iterations).
The ICU controls the maximum number of iterations for the current block so that a given average latency, and hence average throughput, is maintained. Thus, the ICU maintains a latency budget and reduces the maximum number of iterations for the current block when it is behind schedule and increases the maximum number of iterations when it is ahead of schedule. One practical consequence of this approach is that the decoder will have to buffer incoming blocks of channel outputs since these typically arrive at a fixed speed. For example, a decoder designed to operate at an average speed dictated by 10 iterations will need to process some blocks for 20 iterations and will need to buffer incoming channel outputs during this time. More generally, the buffer fills up when the decoder is running behind schedule. Thus, the control algorithm used is a function of how large the buffer is for storing incoming blocks of channel measurements. Since this is a large amount of memory in typical implementations, it is desirable to buffer as few blocks as possible. Fortunately, the advantages of using an ICU can be obtained when buffering only a small number of additional channel measurements.
Augmenting an iterative decoder using early stopping with an ICU results in what we refer to as an early stopping system. FIG. 5 is a simplified illustration of an early stopping system in which measurements (500) from the channel are written to a buffer which may hold several received codeword blocks. Channel measurements are then converted to channel metrics (510), which are input to the decoder in accordance with known techniques. The ICU, configured with a prescribed target average number of decoder iterations, tAVG (530), and a maximum number of decoder iterations, tMAX (540), monitors the buffer status (520) and sets the maximum iteration count, TMAX, (550), for the present block to be decoded. New channel measurements may be available when the decoder finishes and outputs decoded bits (560).
Relative to a decoder using a fixed number of iterations, an early stopping system may increase guaranteed throughput at the expense of increased storage and increased maximum decoding latency. The maximum decoding latency increases because some blocks will wait in the buffer before being processed. Thus, an early stopping system allows one to translate average throughput improvements of an early stopping decoder within the practical constraints of a finite maximum latency and finite storage resources.
An early stopping system allows for two modes of decoder operation: (i) fixed-iterations operation; and (ii) early stopping operation. In fixed-iteration operation, the latency for each decoding block is fixed. In early stopping operation, the latency for each decoding block is variable, but the maximum latency experienced by any block is fixed. If both decoding methods use the same maximum number of iterations, the early stopping operation will result in larger maximum latency. As an example, a fixed-iteration decoder may operate with 20 iterations at a throughput of 100 Megabits per second (Mbps) and a fixed latency of 1 millisecond (msec) per decoding block. An early stopping system operating with an average of 10 iterations may provide a throughput of 200 Mbps and maximum latency of 4 msec for any decoding block.
Iterative decoders using conventional early stopping can realize an improvement in error rate performance relative to an iterative decoder running a number of iterations equal to the average number of iterations for the conventional early stopping algorithm. However, if a higher throughput is desired (i.e., a lower number of average iterations), conventional early stopping cannot be used. In this case, the designer would use a fixed number of iterations corresponding to the desired throughput at the expense of a significant degradation in error rate performance.
Thus, it is desirable to have an early stopping system that allows for greater granularity in the trade-off between decoder throughput and maximum latency. Continuing the above example, suppose that it is desired to achieve a throughput of 400 Mbps, and a maximum decoding latency of more than 10 msec is acceptable. This requires an increase in throughput by a factor of 4 relative to the fixed iteration decoder. One option is to use a fixed-iteration decoder and set the maximum number of iterations to 5 (i.e., 20/4). This approach, however, will result in significant degradation in BER performance if the decoder does not approach convergence in 5 iterations. A standard early stopping rule will also not achieve the desired result. This is because early stopping rules are designed to minimize the average number of iterations required to achieve performance near that of a decoder than runs to convergence. Thus, techniques that overcome these and other shortcomings of conventional methods are desired.